package cn.aylog.algorithm;

import java.util.Arrays;

/**
 * 选择排序
 */
public class SelectSort {
    public static void main(String[] args) {
//        int arr[] = {3, 9, -1, 10, 20};
//        selectSort(arr);
//        Arrays.stream(arr).forEach(i -> System.out.printf("%d ", i));
        int arr1[] = new int[80000];
        for(int i=0; i<80000; i++) {
            int temp = (int)(Math.random()*800000);
            arr1[i] = temp;
        }
        long start = System.currentTimeMillis();
        selectSort(arr1); // 2361
        long end = System.currentTimeMillis();
        System.out.println("selectSort耗时: " + (end - start));

    }

    public static void selectSort(int arr[]) {
        int len = arr.length;
        int min, minIndex;
        long cnt = 0;
        for(int x=0; x<len-1; x++) {
            min = arr[x];
            minIndex = x;
            for(int y=x+1; y<len; y++) {
                cnt++;
                if(min > arr[y]) {
                    min = arr[y];
                    minIndex = y;
                }
            }
            if(minIndex != x) {
                arr[x] = min;
            }
        }
        System.out.println("cnt = " + cnt);
    }
}
